
module Enumerable
  def random()
    self[rand(size).to_i] unless size < 1
  end
  
  def bits_to_int()
    (0...size).inject(0){|total, i| total + (self[i] * 2**i) }
  end
end

module Genetics
  class TooManyBitsError; end
  
  class Genome
    @@num_bits = 8
    
    def self.sized(bits)
      @@num_bits = bits
      return self
    end
    
    def self.size()
      @@num_bits
    end
    
    attr_reader :info
    
    def initialize(n=nil)
      #n = rand(2**@@num_bits) if n.nil?
      n = 0 if n.nil?
      @info = n
      if size > @@num_bits
        @@num_bits = size
        raise TooManyBitsError, "Too many bits! Catch this error to allow for increasing the size of the genome."
      end
    end
    
    # Genes -> organism (Independent of environment)
    def result()
      self.info
    end
    
    # Organism -> survival (Dependent on environment)
    def fitness()
      self.result
    end
    
    def last_result()
      if @last_result.nil?
        @last_result = result
      end
      @last_result
    end
    
    def last_fitness(step)
      if @last_fitness.nil? or step != @last_step
        @last_fitness = fitness
      end
      @last_step = step
      @last_fitness
    end
    
    def clear_last_fitness()
      @last_fitness = nil
      @last_result = nil
    end
    
    def crossover_when(other)
      max_size = [self.size, other.size].max
      one, two = self.info, other.info
      result = (0..max_size).inject(0) do |total, i|
        one, two = two, one if yield(i)
        total + (2**i * one.to_i[i])
      end
      return self.class.new(result)
    end
  
    def uniform_crossover(other)
      max_size = [self.size, other.size].max
      decision = rand(2**max_size)
      return crossover_when(other) {|i| decision[i] == 0 }
    end
    
    def point_crossover(other, n)
      possible_points = (0...size).to_a
      points = []
      n.times { points.push(possible_points.delete_at(rand(possible_points.size))) }
      return crossover_when(other) {|i| points.include?(i) }
    end
    
    def one_point_crossover(other)
      point_crossover(other, 1)
    end
    
    def two_point_crossover(other)
      point_crossover(other, 2)
    end
    
    def mutate(prob=0.05)
      mutated = (0...@@num_bits).map{|i| rand(0) >= prob ? info[i] : info[i] ^ 1}
      self.class.new(mutated.bits_to_int)
    end
    
    def size()
      @info.to_s(2).size
    end
    
    def to_s()
      @info.to_s(2).rjust(@@num_bits,'0')
    end
  end
  
  class GeneticAlgorithm
    attr_reader :population, :best, :best_step
    
    def initialize(population, selection_size, klass=Genome)
      if population.is_a? Integer
        @population = (0...population).to_a.map { klass.new(0).mutate(0.5) }
      elsif population.is_a? Array
        @population = population
      else
        raise ArgumentError, "population must be an Integer or an Array of Genome."
      end
      @selection_size = selection_size
    end
    
    def fittest(n=@selection_size)
      #@population.each { |member| member.clear_last_fitness }
      @population.sort_by { |member| member.last_fitness(@i_step) }[-n..-1]
    end
    
    def mate(pool)
      pool.random.two_point_crossover(pool.random)
    end
    
    def mutate(genome)
      genome.mutate(0.05)
    end
    
    def remember_best()
      current = fittest(1).first
      if @best.nil? || current.last_fitness(@i_step) > @best.fitness
        @best = current
        @best_step = @i_step
      end
    end
  
    def step()
      survivors = fittest
      @population = (0...@population.size).map do |i|
        mutate(mate(survivors))
      end
      remember_best()
      return @best
    end
    
    def run(steps, &block)
      @n_steps = steps
      steps.times do |i|
        @i_step = i
        step()
        block.call(i) if block
      end
      @best
    end
    
    def genome_s(b=fittest(1).first, i=@i_step)
      "#{i}: #{b} => #{b.result} (#{b.last_fitness(@i_step)})"
    end
    
    def best_s()
      genome_s(best, best_step)
    end
  end
end

if $0 == __FILE__
  include Genetics
  g = GeneticAlgorithm.new(6,2)
  best = g.run(50) { puts "#{g.fittest(g.population.size)} (#{g.fittest(1).first})" }
  puts "Fittest genome is: #{g.genome_s(best)}"
end